/*
 * @Author: szx
 * @Date: 2021-11-17 14:09:51
 * @LastEditTime: 2021-11-17 14:34:57
 * @Description:
 * @FilePath: \leetcode\1-99\40\40.js
 */
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
    candidates.sort();
    const res = [];
    const dfs = (start, temp, sum, vis) => {
        if (sum >= target) {
            // 爆掉了，不用继续选数了
            if (sum == target) {
                // 加入解集
                res.push(temp.slice()); // temp的拷贝
            }
            return; // 结束当前递归
        }
        for (let i = start; i < candidates.length; i++) {
            // // 枚举出选择，从start开始
            if (i >= 1 && candidates[i] == candidates[i - 1] && vis[i] == false) {
                continue;
            }
            vis[i] = true;
            temp.push(candidates[i]); // 加入“部分解”
            dfs(i + 1, temp, sum + candidates[i]); // 往下继续选择，同时sum累加上当前数字
            temp.pop(); // 撤销选择
            vis[i] = false;
        }
    };
    const vis = new Array(candidates.length + 1).fill(false);
    console.log(vis);
    dfs(0, [], 0, vis);
    return res;
};
console.log(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8));
